---
layout: api-page
title: "request/complement.js"
id: api
---

<main class="api-documentation-page">
  

  
  
      
<h2>
    request/complement.js
</h2>
<section>
    <article>
        <pre class="prettyprint source linenums"><code>var hasIntersection = require("falcor-path-utils").hasIntersection;
var arraySlice = require("./../support/array-slice");
var arrayConcat = require("./../support/array-concat");
var iterateKeySet = require("falcor-path-utils").iterateKeySet;

/**
 * Figures out what paths in requested pathsets can be
 * deduped based on existing optimized path tree provided.
 *
 * ## no deduping possible:
 *
 * if no existing requested sub tree at all for path,
 * just add the entire path to complement.
 *
 * ## fully deduped:
 *
 * if required path is a complete subset of given sub tree,
 * just add the entire path to intersection
 *
 * ## partial deduping:
 *
 * if some part of path, when ranges are expanded, is a subset
 * of given sub tree, then add only that part to intersection,
 * and all other parts of this path to complement
 *
 * To keep `depth` argument be a valid index for optimized path (`oPath`),
 * either requested or optimized path is sent in pre-initialized with
 * some items so that their remaining length matches exactly, keeping
 * remaining ranges in those pathsets 1:1 in correspondence
 *
 * Note that positive `depthDiff` value means that requested path is
 * longer than optimized path, and we need to pre-initialize current
 * requested path with that many offset items, so that their remaining
 * length matches. Similarly, negative `depthDiff` value means that
 * optimized path is longer, and we pre-initialize optimized path with
 * those many items. Note that because of the way requested and
 * optimized paths are accumulated from what user requested in model.get
 * (see onMissing.js), it is not possible for the pre-initialized paths
 * to have any ranges in them.
 *
 * `intersectionData` is:
 * [ requestedIntersection, optimizedComplement, requestedComplement ]
 * where `requestedIntersection` is matched requested paths that can be
 * deduped, `optimizedComplement` is missing optimized paths, and
 * `requestedComplement` is requested counterparts of those missing
 * optimized paths
 */
module.exports = function complement(requested, optimized, depthDifferences, tree) {
    var optimizedComplement = [];
    var requestedComplement = [];
    var requestedIntersection = [];
    var intersectionLength = -1, complementLength = -1;

    for (var i = 0, len = optimized.length; i &lt; len; ++i) {
        var oPath = optimized[i];
        var rPath = requested[i];
        var depthDiff = depthDifferences[i];
        var subTree = tree[oPath.length];

        // no deduping possible
        if (!subTree) {
            optimizedComplement[++complementLength] = oPath;
            requestedComplement[complementLength] = rPath;
            continue;
        }
        // fully deduped
        if (hasIntersection(subTree, oPath, 0)) {
            requestedIntersection[++intersectionLength] = rPath;
            continue;
        }

        // partial deduping
        var intersectionData = findPartialIntersections(
            rPath,
            oPath,
            subTree,
            depthDiff &lt; 0 ? -depthDiff : 0,
            depthDiff > 0 ? arraySlice(rPath, 0, depthDiff) : [],
            depthDiff &lt; 0 ? arraySlice(oPath, 0, -depthDiff) : [],
            depthDiff);
        for (var j = 0, jLen = intersectionData[0].length; j &lt; jLen; ++j) {
            requestedIntersection[++intersectionLength] = intersectionData[0][j];
        }
        for (var k = 0, kLen = intersectionData[1].length; k &lt; kLen; ++k) {
            optimizedComplement[++complementLength] = intersectionData[1][k];
            requestedComplement[complementLength] = intersectionData[2][k];
        }
    }

    if (!requestedIntersection.length) {
        return null;
    }
    return [requestedIntersection, optimizedComplement, requestedComplement];
};

/**
 * Recursive function to calculate intersection and complement paths in 2 given
 * pathsets at a given depth
 * Parameters:
 *  - `requestedPath`: full requested path (can include ranges)
 *  - `optimizedPath`: corresponding optimized path (can include ranges)
 *  - `currentTree`: path map for in-flight request, against which to dedupe
 *  - `depth`: index of optimized path that we are trying to match with `currentTree`
 *  - `rCurrentPath`: current accumulated requested path by previous recursive
 *                    iterations. Could also have been pre-initialized as stated
 *                    above.
 *                    This path cannot contain ranges, instead contains a key
 *                    from the range, representing one of the individual paths
 *                    in `requestedPath` pathset
 *  - `oCurrentPath`: corresponding accumulated optimized path, to be matched
 *                    with `currentTree`. Could have been pre-initialized.
 *                    Cannot contain ranges, instead contains a key from the
 *                    range at given `depth` in `optimizedPath`
 *  - `depthDiff`: difference in length between `requestedPath` and `optimizedPath`
 *
 *  Example scenario:
 *      - requestedPath: ['lolomo', 0, 0, 'tags', { from: 0, to: 2 }]
 *      - optimizedPath: ['videosById', 11, 'tags', { from: 0, to: 2 }]
 *      - currentTree: { videosById: 11: { tags: { 0: null, 1: null }}}
 *      // since requested path is longer, optimized path index starts from depth 0
 *      // and accumulated requested path starts pre-initialized (rCurrentPath)
 *      - depth: 0
 *      - rCurrentPath: ['lolomo']
 *      - oCurrentPath: []
 *      - depthDiff: 1
 */
function findPartialIntersections(requestedPath, optimizedPath, currentTree, depth, rCurrentPath, oCurrentPath, depthDiff) {
    var intersections = [];
    var rComplementPaths = [];
    var oComplementPaths = [];
    // iterate over optimized path, looking for deduping opportunities
    for (; depth &lt; optimizedPath.length; ++depth) {
        var key = optimizedPath[depth];
        var keyType = typeof key;

        // if range key is found, start inner loop to iterate over all keys in range
        // and add intersections and complements from each iteration separately.
        // range keys branch-out like this, providing individual deduping
        // opportunities for each inner key
        if (key &amp;&amp; keyType === "object") {
            var note = {};
            var innerKey = iterateKeySet(key, note);

            while (!note.done) {
                var nextTree = currentTree[innerKey];
                if (nextTree === undefined) {
                    // if no next sub tree exists for an inner key, it's a dead-end
                    // and we can add this to complement paths
                    var oPath = oCurrentPath.concat(
                        innerKey,
                        arraySlice(
                            optimizedPath,
                            depth + 1));
                    oComplementPaths[oComplementPaths.length] = oPath;
                    var rPath = rCurrentPath.concat(
                        innerKey,
                        arraySlice(
                            requestedPath,
                            depth + 1 + depthDiff));
                    rComplementPaths[rComplementPaths.length] = rPath;
                } else if (depth === optimizedPath.length - 1) {
                    // reaching the end of optimized path means that we found a
                    // corresponding node in the path map tree every time,
                    // so add current path to successful intersections
                    intersections[intersections.length] = arrayConcat(rCurrentPath, [innerKey]);
                } else {
                    // otherwise keep trying to find further partial deduping
                    // opportunities in the remaining path!
                    var intersectionData = findPartialIntersections(
                        requestedPath,
                        optimizedPath,
                        nextTree,
                        depth + 1,
                        arrayConcat(rCurrentPath, [innerKey]),
                        arrayConcat(oCurrentPath, [innerKey]),
                        depthDiff);
                    for (var j = 0, jLen = intersectionData[0].length; j &lt; jLen; ++j) {
                        intersections[intersections.length] = intersectionData[0][j];
                    }
                    for (var k = 0, kLen = intersectionData[1].length; k &lt; kLen; ++k) {
                        oComplementPaths[oComplementPaths.length] = intersectionData[1][k];
                        rComplementPaths[rComplementPaths.length] = intersectionData[2][k];
                    }
                }
                innerKey = iterateKeySet(key, note);
            }
            break;
        }

        // for simple keys, we don't need to branch out. looping over `depth`
        // here instead of recursion, for performance
        currentTree = currentTree[key];
        oCurrentPath[oCurrentPath.length] = optimizedPath[depth];
        rCurrentPath[rCurrentPath.length] = requestedPath[depth + depthDiff];

        if (currentTree === undefined) {
            // if dead-end, add this to complements
            oComplementPaths[oComplementPaths.length] =
                arrayConcat(oCurrentPath, arraySlice(optimizedPath, depth + 1));
            rComplementPaths[rComplementPaths.length] =
                arrayConcat(rCurrentPath, arraySlice(requestedPath, depth + depthDiff + 1));
            break;
        } else if (depth === optimizedPath.length - 1) {
            // if reach end of optimized path successfully, add to intersections
            intersections[intersections.length] = rCurrentPath;
        }
        // otherwise keep going
    }

    // return accumulated intersection and complement pathsets
    return [intersections, oComplementPaths, rComplementPaths];
}

</code></pre>
    </article>
</section>
  

  
</main>



        
        <!--
          In case someone comes along later and sees the active item on the
          toc acting weirdly, hopefully they'll see this comment. This page, unlike
          any seen during development, has multiple 'docs' passed to container.tmpl.
          To debug it and enhance the page as needed, I would suggest looking there first.
        -->
        

        <!-- Generate the table of contents -->
        <nav class="table-of-contents api-doc-toc">
            <ul class="nav">
                <li>
                    <a href="DataSource.html">Classes</a>
                    <ul class="toc-api-classes">
                        
                            <li class="toc-api-class ">
                                <a href="DataSource.html" data-target="#DataSource">DataSource</a>
                                
                                

    <ul class="toc-api-subgroup toc-api-subgroup-methods">
        <li>
            <span class="toc-api-subgroup-title">Methods</span>
        </li>
        
            <li class="toc-api-subgroup-item">
                <a href="DataSource.html#call" data-target="#call">call</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="DataSource.html#get" data-target="#get">get</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="DataSource.html#set" data-target="#set">set</a>
            </li>
         
    </ul>


                                


                                


                            </li>
                        
                            <li class="toc-api-class ">
                                <a href="FromEsObserverAdapter.html" data-target="#FromEsObserverAdapter">FromEsObserverAdapter</a>
                                
                                


                                


                                


                            </li>
                        
                            <li class="toc-api-class ">
                                <a href="HttpDataSource.html" data-target="#HttpDataSource">HttpDataSource</a>
                                
                                

    <ul class="toc-api-subgroup toc-api-subgroup-methods">
        <li>
            <span class="toc-api-subgroup-title">Methods</span>
        </li>
        
            <li class="toc-api-subgroup-item">
                <a href="HttpDataSource.html#call" data-target="#call">call</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="HttpDataSource.html#get" data-target="#get">get</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="HttpDataSource.html#set" data-target="#set">set</a>
            </li>
         
    </ul>


                                


                                


                            </li>
                        
                            <li class="toc-api-class ">
                                <a href="Model.html" data-target="#Model">Model</a>
                                
                                

    <ul class="toc-api-subgroup toc-api-subgroup-methods">
        <li>
            <span class="toc-api-subgroup-title">Methods</span>
        </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#_setMaxSize" data-target="#_setMaxSize">_setMaxSize</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#asDataSource" data-target="#asDataSource">asDataSource</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#batch" data-target="#batch">batch</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#boxValues" data-target="#boxValues">boxValues</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#call" data-target="#call">call</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#deref" data-target="#deref">deref</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#get" data-target="#get">get</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#getCache" data-target="#getCache">getCache</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#getPath" data-target="#getPath">getPath</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#getVersion" data-target="#getVersion">getVersion</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#invalidate" data-target="#invalidate">invalidate</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#preload" data-target="#preload">preload</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#set" data-target="#set">set</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#setCache" data-target="#setCache">setCache</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#treatErrorsAsValues" data-target="#treatErrorsAsValues">treatErrorsAsValues</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#unbatch" data-target="#unbatch">unbatch</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#unboxValues" data-target="#unboxValues">unboxValues</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#withoutDataSource" data-target="#withoutDataSource">withoutDataSource</a>
            </li>
         
    </ul>


                                

    <ul class="toc-api-subgroup toc-api-subgroup-types">
        <li>
            <span class="toc-api-subgroup-title">Types</span>
        </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#~comparator" data-target="#\~comparator">comparator</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#~errorSelector" data-target="#\~errorSelector">errorSelector</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Model.html#~onChange" data-target="#\~onChange">onChange</a>
            </li>
         
    </ul>


                                


                            </li>
                        
                            <li class="toc-api-class ">
                                <a href="ModelResponse.html" data-target="#ModelResponse">ModelResponse</a>
                                
                                

    <ul class="toc-api-subgroup toc-api-subgroup-methods">
        <li>
            <span class="toc-api-subgroup-title">Methods</span>
        </li>
        
            <li class="toc-api-subgroup-item">
                <a href="ModelResponse.html#forEach" data-target="#forEach">forEach</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="ModelResponse.html#progressively" data-target="#progressively">progressively</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="ModelResponse.html#subscribe" data-target="#subscribe">subscribe</a>
            </li>
         
    </ul>


                                


                                


                            </li>
                        
                            <li class="toc-api-class ">
                                <a href="ModelResponseObserver.html" data-target="#ModelResponseObserver">ModelResponseObserver</a>
                                
                                


                                


                                


                            </li>
                        
                            <li class="toc-api-class ">
                                <a href="Observable.html" data-target="#Observable">Observable</a>
                                
                                

    <ul class="toc-api-subgroup toc-api-subgroup-methods">
        <li>
            <span class="toc-api-subgroup-title">Methods</span>
        </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Observable.html#forEach" data-target="#forEach">forEach</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Observable.html#subscribe" data-target="#subscribe">subscribe</a>
            </li>
         
    </ul>


                                

    <ul class="toc-api-subgroup toc-api-subgroup-types">
        <li>
            <span class="toc-api-subgroup-title">Types</span>
        </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Observable.html#~onCompletedCallback" data-target="#\~onCompletedCallback">onCompletedCallback</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Observable.html#~onErrorCallback" data-target="#\~onErrorCallback">onErrorCallback</a>
            </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Observable.html#~onNextCallback" data-target="#\~onNextCallback">onNextCallback</a>
            </li>
         
    </ul>


                                


                            </li>
                        
                            <li class="toc-api-class ">
                                <a href="Subscription.html" data-target="#Subscription">Subscription</a>
                                
                                

    <ul class="toc-api-subgroup toc-api-subgroup-methods">
        <li>
            <span class="toc-api-subgroup-title">Methods</span>
        </li>
        
            <li class="toc-api-subgroup-item">
                <a href="Subscription.html#dispose" data-target="#dispose">dispose</a>
            </li>
         
    </ul>


                                


                                


                            </li>
                        
                            <li class="toc-api-class ">
                                <a href="ToEsSubscriptionAdapter.html" data-target="#ToEsSubscriptionAdapter">ToEsSubscriptionAdapter</a>
                                
                                


                                


                                


                            </li>
                        
                    </ul>
                </li>
                <li class="toc-api-type-list ">
                    <a href="global.html">Global Types</a>
                    <ul class="toc-api-types">
                        
                            <li class="toc-api-type">
                                <a href="global.html#Atom" data-target="#Atom">Atom</a>
                            </li>
                        
                            <li class="toc-api-type">
                                <a href="global.html#JSONEnvelope" data-target="#JSONEnvelope">JSONEnvelope</a>
                            </li>
                        
                            <li class="toc-api-type">
                                <a href="global.html#JSONGraph" data-target="#JSONGraph">JSONGraph</a>
                            </li>
                        
                            <li class="toc-api-type">
                                <a href="global.html#JSONGraphEnvelope" data-target="#JSONGraphEnvelope">JSONGraphEnvelope</a>
                            </li>
                        
                            <li class="toc-api-type">
                                <a href="global.html#Key" data-target="#Key">Key</a>
                            </li>
                        
                            <li class="toc-api-type">
                                <a href="global.html#KeySet" data-target="#KeySet">KeySet</a>
                            </li>
                        
                            <li class="toc-api-type">
                                <a href="global.html#Path" data-target="#Path">Path</a>
                            </li>
                        
                            <li class="toc-api-type">
                                <a href="global.html#PathSet" data-target="#PathSet">PathSet</a>
                            </li>
                        
                            <li class="toc-api-type">
                                <a href="global.html#PathValue" data-target="#PathValue">PathValue</a>
                            </li>
                        
                            <li class="toc-api-type">
                                <a href="global.html#Range" data-target="#Range">Range</a>
                            </li>
                        
                    </ul>
                </li>
            </ul>
        </nav>





